package binarysearch;

/**
 * 4.寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 */
public class findMedianSortedArrays {
    /**
     * hot100一刷
     * hot100二刷
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        int half = (m + n + 1) / 2; // 左侧部分的总元素数

        while (left <= right) {
            // 在 nums1 中尝试分割位置 i
            int i = (left + right) / 2;
            // 在 nums2 中对应的分割位置 j
            int j = half - i;

            // 确定 nums1 和 nums2 的边界值
            int leftMax1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int rightMin1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int leftMax2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int rightMin2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            // 检查分割条件
            if (leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
                // 如果总长度是奇数，中位数是左侧最大值
                if ((m + n) % 2 == 1) {
                    return Math.max(leftMax1, leftMax2);
                } else {
                    // 如果总长度是偶数，中位数是左侧最大值和右侧最小值的平均值
                    return (Math.max(leftMax1, leftMax2) + Math.min(rightMin1, rightMin2)) / 2.0;
                }
            } else if (leftMax1 > rightMin2) {
                // i 太大，需要向左移动
                right = i - 1;
            } else {
                // i 太小，需要向右移动
                left = i + 1;
            }
        }

        // 如果未找到合适的分割位置，抛出异常
        throw new IllegalArgumentException("输入数组无效！");
    }
}
